﻿#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<windows.h>//系统工具库
#include<iostream>
#include<iomanip>
#include<fstream>

using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MVNum 100

typedef char ET;//顶点data
typedef int AUT;//其他值(权值等)

typedef struct AN  //边节点
{
	int adjvex;//边指向的顶点位置的数据域
	AN* nextarc;//下一条边
	AUT info;//权值等其他学校
}AN;
typedef struct VN   //顶点信息
{
	ET data;//顶点名
	AN* firstarc;//顶点的第一个边节点
}VN,VNM[MVNum];//VNJ表示100个顶点数组
typedef struct ALG
{
	VNM vertices;              //邻接表 
	int vexnum, arcnum;      //图的当前顶点数和边数 
}ALG;

bool visited[MVNum];//初值为flash

enum alg
{
	退出程序,
	建邻接表,
	深度遍历,
	广度遍历
};

//借助队列实现广义遍历
//******************************************************************
typedef int EAT;
typedef struct  sq//重定义结构体名为sq
{
	EAT* data;//数据的基地址
	int front;//头指针
	int rear;//尾指针
};
int InitSq(sq* Q)//初始化
{
	Q->data = NULL;//初始化为空
	Q->data = (EAT*)realloc(Q->data, MVNum * sizeof(EAT));//realloc开辟100个ET类型的空间
	Q->front = Q->rear = 0;//头尾指针置空
	if (Q->data == NULL)//如果申请失败则退出
	{
		cout << "内存申请失败！" << endl;
		exit(OVERFLOW);
	}
	return OK;
}
int SqDestroy(sq* Q)//销毁队列
{
	if (Q->data == NULL)//若data地址已经为空则直接退出
	{
		return OVERFLOW;
	}

	free(Q->data);//释放data
	Q->data = NULL;
	Q->front = Q->rear = 0;
	return OK;
}
int SqPush(sq* Q, int x)//入队
{
	if (((Q->rear) + 1) % MVNum == Q->front)
	{
		return OVERFLOW;
	}

	Q->data[Q->rear] = x;//x入队尾
	Q->rear = ((Q->rear) + 1) % MVNum;//队尾指向队尾的下一个
	return OK;
}

EAT SqPop(sq* Q)//出队
{
	if ((Q->front) == (Q->rear))
	{
		printf("队空！\n");
	}

	EAT e;
	e = Q->data[Q->front];
	Q->front = ((Q->front) + 1) % MVNum;
	return e;
}
//***********************************************************************

void menu()
{
	printf("**************************\n");
	printf("*  图的实现—建立邻接表  *\n");
	printf("**************************\n");
	printf("*0.退出程序    1.建邻接表*\n");
	printf("*2.深度遍历    3.广度遍历*\n");
	printf("**************************\n");
}

int Locatevex(ALG G, ET x)//在顺序表中查找某个顶点
{
	for (int i = 0; i < G.vexnum; ++i)
	{
		if (x == G.vertices[i].data)
		{
			return i;
		}
	}
	return -1;
}

int  CreateUDG(ALG &G)//建立邻接表
{
	printf("请输入顶点数>");
	cin>>G.vexnum;
	printf("请输入边数>");
	cin>>G.arcnum;
	system("cls");
	for (int i = 0; i < G.vexnum; ++i)
	{
		printf("请输入第%d个顶点的值>",i+1);
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	for (int k = 0; k < G.arcnum; ++k)
	{
scan:
		system("cls");
		ET v1, v2;//两个顶点
		printf("第%d条边,请输入边两顶点(空格分隔)>",k+1);
		cin >> v1>>v2;
		int m = Locatevex(G, v1);//在顺序表中查找两顶点的位置
		int n = Locatevex(G, v2);
		if (m != -1 && n != -1)
		{
			AN* p1 = (AN*)malloc(sizeof(AN));//申请两个新的边节点
			AN* p2 = (AN*)malloc(sizeof(AN));

			p1->adjvex = n;
			p1->nextarc = G.vertices[m].firstarc;
			G.vertices[m].firstarc = p1;

			p2->adjvex = m;
			p2->nextarc = G.vertices[n].firstarc;
			G.vertices[n].firstarc = p2;
		}
		else//说明为什么错误
		{
			if (m == -1&&n == -1)
			{
				printf("未找到顶点“%c”和“%c”，请重新输入！\n",v1,v2);
				system("pause");
				goto scan;
			}
			else if (m == -1 && n != -1)
			{
				printf("未找到顶点“%c”，请重新输入！\n", v1);
				system("pause");
				goto scan;
			}
			else if (m != -1 && n == -1)
			{
				printf("未找到顶点“%c”，请重新输入！\n", v2);
				system("pause");
				goto scan;
			}
			
		}
	}
	return OK;
}

void BDFSvid(ALG& G)//刷新visited数组，方便二次遍历
{
	for (int i = 0; i < G.vexnum; i++)
	{
		visited[i] = false;
	}
}


void  DFSALG(ALG G, int x)//深度优先遍历
{
	printf("第%d个顶点的值%c已访问！\n",x, G.vertices[x].data);
	visited[x] = true;//该顶点标记已访问

	AN* p = G.vertices[x].firstarc;//存入顶点第一个边节点的地址

	while (p !=NULL)
	{
		int w = p->adjvex;//w存入顶点在顺序表中的位置信息
		
		if (!visited[w])//如果顶点没有被访问过
		{
			DFSALG(G, w);//访问该顶点的下一个边节点
		}
		p = p->nextarc;//p指向下一个边节点
	}
}

int FirstAdjVex(ALG G,int x)//检查下一个边节点
{
	if (G.vertices[x].firstarc)//判断临界点
	{
		return G.vertices[x].firstarc->adjvex;//返回边节点顺序表中的顶点号
	}
	return -1;
}


int NextAdjVex(ALG G, int u, int w)
{
	AN* p = G.vertices[u].firstarc;//顶点
	while (p)//如果该顶点的边节点不为空
	{
		if (p->adjvex == w && p->nextarc!=NULL)//找当前访问的边节点
		{
			if ((!visited[(p->nextarc->adjvex)]))//判断当前访问节点的下一个边节点是否被访问过
			{
				return p->nextarc->adjvex;//返回当前访问边节点的后面的节点
			}
		}
		p = p->nextarc;//p指向下一个边节点
	}
	return -1;//如果没有则返回-1
}


void BFSALG(ALG G, int x)//广义遍历
{
	sq Q;
	printf("第%d个顶点的值%c已访问！\n", x, G.vertices[x].data);
	visited[x] = true;//该顶点标记已访问
	InitSq(&Q);//初始化队列
	SqPush(&Q, x);
	while (Q.front != Q.rear)
	{
		EAT u=SqPop(&Q);
		for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))//初始化w为当前节点，随后将遍历到的边节点顶点位置传给w，如果无边节点则返回-1
		{
			if (!visited[w])
			{
				printf("第%d个顶点的值%c已访问！\n", w, G.vertices[w].data);
				visited[w] = true;//该顶点标记已访问
				SqPush(&Q, w);//w入队
			}
		}
	}
	SqDestroy(&Q);//销毁队列
}

void ALGDestroy(ALG& G)//销毁邻接表
{
	int x = G.vexnum;
	for (int i=0;i<x;++i)
	{
		G.vertices[i].data = 0;//置空顶点
		G.vertices[i].firstarc = NULL;//置空边链表
	}
}

int main()
{
	ALG G;
	int order = 0;
	do
	{
		system("cls");
		menu();
		printf("请输入选择>");
		cin >> order;
		switch (order)
		{
			case 退出程序:
			{
				system("cls");
				printf("退出程序!\n");
				BDFSvid(G);//重置visited数组为flase
				ALGDestroy(G);//默认从顶点表第一个顶点开始销毁
				break;
			}
			case 建邻接表:
			{
				system("cls");
				CreateUDG(G);
				break;
			}
			case 深度遍历:
			{
			SDBL:
				system("cls");
				BDFSvid(G);//重置visited数组为flase
				ET x = 0;
				printf("请输入遍历起始顶点名>");
				cin >> x;
				int y = Locatevex(G, x);
				if (y == -1)
				{
					printf("该顶点不存在，请重新输入！\n");
					system("pause");
					goto SDBL;
				}
				system("cls");
				printf("深度优先遍历：\n");
				cout << endl;
				DFSALG(G, y);//深度优先遍历
				cout << endl;
				system("pause");
				break;
			}
			case 广度遍历:
			{
			GDBL:
				system("cls");
				BDFSvid(G);//重置visited数组为flase
				ET x = 0;
				printf("请输入遍历起始顶点名>");
				cin >> x;
				int y = Locatevex(G, x);
				if (y == -1)
				{
					printf("该顶点不存在，请重新输入！\n");
					system("pause");
					goto GDBL;
				}
				system("cls");
				printf("广度优先遍历：\n");
				cout << endl;
				BFSALG(G, y);//广度优先遍历
				cout << endl;
				system("pause");
				break;
			}
			default:
			{
				printf("输入错误，请重新输入！\n");
				system("pause");
				break;
			}
		}
	} while (order);
}//代码总长358